package work3;

import java.util.Arrays;
import java.util.Collections;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Random;

/**
 * @author zhangxufeng@meitunmama.com 2019-08-30 14:15:04
 */
public class EpsilonGreedy {

  private static final int T = 100000;  // 尝试次数
  private static final int N = 10;  // 目标次数

  private static Random random = new Random();

  /**
   * N个item的真实质量数据
   */
  private static double[] trueRewards = new double[N];

  /**
   * 通过每次试验的累加，得到了最终N个目标item的评估值
   */
  private static double[] estimatedRewards = new double[N];

  /**
   * 记录了N个item中每个item的选中次数
   */
  private static int[] numberOfTrials = new int[N];

  /**
   * 表示根据我们累加的评估结果，最终有多少次试验是选中了我们推荐的item
   */
  private int totalReward = 0;

  /**
   * 进行Epsilon-Greedy试验的主流程。这里的T表示进行尝试的次数，N表示目标item的个数。在每次试验中，首先会获取一个
   * item，以及是否选中该item。然后将选中的item与历史进行过的评估进行汇总，依次进行累加，从而得到一个比较优秀的
   * 评估结果。在尝试次数足够多的情况下，estimatedRewards与trueRewards的值是基本一致的。totalRewards表示我们
   * 的推荐算法最终会得到用户选中的次数，这个次数越高，则表示该算法越好。
   */
  public void epsilonGreedyExperiment() {
    for (int i = 1; i < T; i++) {
      Map<Integer, Integer> selectedItem = alphaGreedy(N, 0.99);
      Entry<Integer, Integer> entry = selectedItem.entrySet().iterator().next();
      Integer item = entry.getKey();
      Integer reward = entry.getValue();

      totalReward += reward;
      numberOfTrials[item] += 1;
      estimatedRewards[item] = ((numberOfTrials[item] - 1) * estimatedRewards[item]
          + reward) / numberOfTrials[item];
    }

    System.out.println("totalReward=" + totalReward);
    System.out.println("trueRewards: " + Arrays.toString(trueRewards));
    System.out.println("estimatedRewards: " + Arrays.toString(estimatedRewards));
    System.out.println("numberOfTrials: " + Arrays.toString(numberOfTrials));
  }

  /**
   * 使用Epsilon-Greedy算法在目标项目中选择一个item。该算法的基本原理如下：
   * ①首先生成一个随机数，将该值与目标探索概率alpha进行比较，如果小于alpha，则表示此次事件是需要进行尝试的；
   * ②如果要进行尝试，则会从目标item中随机选择一个返回；
   * ③如果不需要进行尝试，则会从当前所有评估的item中选择质量最好的item将其返回；
   * ④通过上面两种方式返回的item，根据该item的实际质量，随机生成一个数字，判断该数字是否落在这个实际质量中，
   *   是，则表示此次选择了该item，否，则表示此次没有选择该item。
   * 最后将进行试验的item和是否选择了该item的二元组返回
   *
   * @param n 目标item个数
   * @param alpha 所选取的进行探索新的item的概率
   * @return 是一个item和是否选中的键值对，键为某个item，值为客户是否选择了该item
   */
  private Map<Integer, Integer> alphaGreedy(int n, double alpha) {
    int item = 0;
    if (random.nextDouble() < alpha) {
      item = random.nextInt(n);
    } else {
      item = maxEstimated();
    }

    int reward = binomial(1, trueRewards[item]);
    return Collections.singletonMap(item, reward);
  }

  /**
   * 该方法的主要作用是进行n次试验，每次试验落在目标概率p内的次数，这里主要是模拟用户会选择目标item的次数
   *
   * @param n 进行试验的次数，这里传入的值为1，因为是模拟用户是否选择目标item
   * @param p 目标概率p，也即表征当前item质量的一个参数，概率越大，质量越好
   * @return 落在目标概率中的次数
   */
  private int binomial(int n, double p) {
    int result = 0;
    for (int i = 0; i < n; i++) {
      double v = random.nextDouble();
      if (Double.compare(v, p) <= 0) {
        result++;
      }
    }

    return result;
  }

  /**
   * 查找当前评估的所有item中，质量最高的item，将其返回。
   * @return 返回质量最高的item的下标
   */
  private int maxEstimated() {
    int result = 0;
    for (int i = 1; i < estimatedRewards.length; i++) {
      if (estimatedRewards[i] > estimatedRewards[result]) {
        result = i;
      }
    }

    return result;
  }


  static {
    for (int i = 0; i < trueRewards.length; i++) {
      trueRewards[i] = random.nextDouble();
    }
  }

  public static void main(String[] args) {
    EpsilonGreedy epsilonGreedy = new EpsilonGreedy();
    epsilonGreedy.epsilonGreedyExperiment();
  }


}
